package com.test.daily.leetcode.y2022.m07.day0719.v02;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/19 上午 10:51
 * @version: 1.0
 */
public class Solution {
    public static class Node{
        Node left;
        Node right;
        int value;
        public Node(int value){
            this.value = value;
        }
    }
    public static int maxDistance(Node head){
        List<Node> list = new ArrayList<>();
        HashMap<Node, Node> map = new HashMap<>();
        preFill(head, list);
        putParent(head, map);
        int max = -1;
        for(int i = 0; i < list.size(); i++){
            for(int j = i + 1; j < list.size();j++){
                max = Math.max(max, getDistance(map, list.get(i), list.get(j)));
            }
        }
        return max;
    }
    public static int getDistance(HashMap<Node, Node> map, Node o1, Node o2){
        Node h1 = o1;
        Node h2 = o2;
        HashSet<Node> o1Set = new HashSet<>();
        HashSet<Node> o2Set = new HashSet<>();
        while(h1 != null){
            o1Set.add(h1);
            h1 = map.get(h1);
        }
        while(!o1Set.contains(h2)){
            h2 = map.get(h2);
        }
        Node lowestAncestor = h2;
        int h = 1;
        h1 = o1;
        h2 = o2;
        while(h1 != lowestAncestor){
            h++;
            h1 = map.get(h1);
        }
        while(h2 != lowestAncestor){
            h++;
            h2 = map.get(h2);
        }
        return h;
    }
    public static void putParent(Node head, HashMap<Node, Node> map){
        if(head.left != null){
            map.put(head.left, head);
            putParent(head.left, map);
        }
        if(head.right != null){
            map.put(head.right, head);
            putParent(head.right, map);
        }
    }
    public static void preFill(Node head, List<Node> list){
        if(head == null){
            return;
        }
        list.add(head);
        preFill(head.left, list);
        preFill(head.right, list);
    }

    public static class Info{
        int maxDistance;
        int height;
        public Info(int maxDistance, int height){
            this.maxDistance = maxDistance;
            this.height = height;
        }
    }
    public static int maxDistance2(Node head){
        return process(head).maxDistance;
    }
    public static Info process(Node head){
        if(head == null){
            return new Info(0, 0);
        }
        Info leftInfo = process(head.left);
        Info rightInfo = process(head.right);
        int height = Math.max(leftInfo.height, rightInfo.height) + 1;
        int p1 = leftInfo.maxDistance;
        int p2 = rightInfo.maxDistance;
        int p3 = leftInfo.height + rightInfo.height + 1;
        return new Info(Math.max(p3, Math.max(p1, p2)), height);
    }
}
